package com.liam.leetcode;


import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class 解数独_37 {



    public static void main(String[] args) {
        Long begin = System.currentTimeMillis();
        // 初始化原始数组
        Integer[][] result = init();

        int i= 0;
        while (!build(result)){
            i ++;
            System.out.println("第"+i+"次");
            result =  init();
        }
        print(result);
        System.out.println(System.currentTimeMillis() - begin);
    }

    private static boolean build(Integer[][] result) {
        for (int i = 0; i < result.length; i++) {
            for (int j = 0; j < result[i].length; j++) {
                if (result[i][j] == null) {
                    if(!set(i, j, result)){
                        return false;

                    }
                }
            }
        }
        return true;
    }

    private static boolean set(int i, int j, Integer[][] result) {
        // 获取小方块
        Integer[][] small = getSmall(result, getSmallNum(i, j));

        List<Integer> all = getList(small);
        // 获取横纵 已存在的值
        List<Integer> HZ = getHZ(result, i, j);
        all.addAll(HZ);

        List<Integer> nums = getNums();
        nums.removeAll(all);
        if(nums.size() == 0){
           return false;
        }
        result[i][j] = nums.get(getRandom(0,nums.size()));
        return true;
    }
    public static int getRandom(int min,int max){
        if(min == max){
            return min;
        }
        return new Random().nextInt(max) % (max - min + 1) + min;
    }


    private static List<Integer> getNums() {
        List<Integer> nums = new ArrayList<Integer>();
        for (int i = 1; i < 10; i++) {
            nums.add(i);
        }
        return nums;
    }

    private static List<Integer> getList(Integer[][] result) {
        List<Integer> temp = new ArrayList<Integer>();
        for (int i = 0; i < result.length; i++) {
            for (int j = 0; j < result[i].length; j++) {
                if (result[i][j] != null) {
                    temp.add(result[i][j]);
                }
            }
        }
        return temp;
    }

    private static List<Integer> getHZ(Integer[][] result, int ii, int jj) {
        List<Integer> temp = new ArrayList<Integer>();
        for (int i = 0; i < 9; i++) {
            if (result[i][jj] != null) {
                temp.add(result[i][jj]);
            }
        }
        for (int j = 0; j < 9; j++) {
            if (result[ii][j] != null) {
                temp.add(result[ii][j]);
            }
        }
        return temp;
    }

    private static Integer getSmallNum(int i, int j) {
        if (i < 3) {
            return j < 3 ? 1 : j < 6 ? 2 : 3;
        } else if (i < 6) {
            return j < 3 ? 4 : j < 6 ? 5 : 6;
        } else {
            return j < 3 ? 7 : j < 6 ? 8 : 9;
        }
    }

    private static Integer[][] getSmall(Integer[][] result, int num) {
        Integer[][] temp = new Integer[3][3];

        int minI = num <= 3 ? 0 : num <= 6 ? 3 : 6;

        int minJ = num == 1 || num == 4 || num == 7 ? 0 : num == 2 || num == 5 || num == 8 ? 3 : 6;

        int maxI = minI + 3;

        int i = 0;
        for (; minI < maxI; minI++) {
            int maxJ = minJ + 3;
            int tempMinJ = minJ;
            int j = 0;
            for (; tempMinJ < maxJ; tempMinJ++) {

                temp[i][j] = result[minI][tempMinJ];
//                System.out.println("getSmall " + i + ":" + j);

                j++;
            }
            i++;

        }
        return temp;
    }

    private static void print(Integer[][] result) {
        for (int i = 0; i < result.length; i++) {
            for (int j = 0; j < result[i].length; j++) {
                System.out.print(result[i][j] + "\t");
            }
            System.out.println("");
        }
    }

    private static Integer[][] init() {
        Integer[][] result = new Integer[9][9];
        result[0][0] = 5;
        result[0][1] = 3;
        result[0][4] = 7;

        result[1][0] = 6;
        result[1][3] = 1;
        result[1][4] = 9;
        result[1][5] = 5;

        result[2][1] = 9;
        result[2][2] = 8;
        result[2][7] = 6;

        result[3][0] = 8;
        result[3][4] = 6;
        result[3][8] = 3;

        result[4][0] = 4;
        result[4][3] = 8;
        result[4][5] = 3;
        result[4][8] = 1;

        result[5][0] = 7;
        result[5][4] = 2;
        result[5][8] = 6;

        result[6][1] = 6;
        result[6][6] = 2;
        result[6][7] = 8;

        result[7][3] = 4;
        result[7][4] = 1;
        result[7][5] = 9;
        result[7][8] = 5;

        result[8][4] = 8;
        result[8][7] = 7;
        result[8][8] = 9;

        return result;
    }
}
